
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

////法一：新定义链表
//    public ListNode reverseList(ListNode head) {
//        if (head == null) return null;
//        ListNode newList = new ListNode(head.val);
//        while (head.next != null){
//            newList = addAtHead(newList,head.next.val);
//            head = head.next;
//        }
//        return newList;
//
//
//    }
//
//    private ListNode addAtHead(ListNode newList, int val) {
//        ListNode newNode = new ListNode(val);
//        newNode.next = newList;
//        newList = newNode;
//        return newList;
//    }


//    // 法二：原地调转指针方向
//    public ListNode reverseList(ListNode head) {
//
//        ListNode cur = head;
//        ListNode pre = null;
//
//        while (cur != null){
//            ListNode temp = pre;
//            pre = cur;
//            cur = cur.next;
//            pre.next = temp;
//        }
//        return pre;
//    }

    //法三：递归 骚操作
    public ListNode reverseList(ListNode head) {
        //递归中止条件
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}